//
// Created by Semir on 2020/6/10.
//

#include <iostream>
#include "../Util/Tree.h"

using namespace std;

TreeNode* target = nullptr;

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) {
        return nullptr;
    }
    bool isOne = false;
    if (root->val == p->val || root->val == q->val) {
        isOne = true;
    }
    //开启递归左子树，返回left
    TreeNode* left = nullptr;
    if (root->left != nullptr) {
        left = lowestCommonAncestor(root->left, p, q);
    }
    //开启递归右子树，返回right
    TreeNode* right = nullptr;
    if (root->right != nullptr) {
        right = lowestCommonAncestor(root->right, p, q);
    }
    if (target != nullptr) {
        return target;
    }
    //如果左右子树都不为空，返回root节点，并设全局指针为root
    if (left != nullptr && right != nullptr) {
        target = root;
        return target;
    }
    //如果左右子树有一个不为空，返回它
    if (left != nullptr || right != nullptr) {
        if (isOne) {
            target = root;
            return target;
        } else {
            return left != nullptr ? left : right;
        }
    }
    return isOne ? root : target;
}

int main() {
    return 0;
}